from typing import List

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def is_palindrome(s: str) -> bool:
            """判断字符串是否为回文串"""
            return s == s[::-1]
        
        def backtrack(start: int, path: List[str]):
            """回溯函数
            start: 当前开始位置
            path: 当前路径（已分割的子串列表）
            """
            # 如果已经遍历完整个字符串，将当前路径加入结果
            if start == len(s):
                result.append(path[:])
                return
            
            # 尝试从当前位置开始的所有可能分割
            for end in range(start + 1, len(s) + 1):
                # 获取当前子串
                substring = s[start:end]
                # 如果当前子串是回文串，继续回溯
                if is_palindrome(substring):
                    path.append(substring)
                    backtrack(end, path)
                    path.pop()  # 回溯，移除最后添加的子串
        
        result = []
        backtrack(0, [])
        return result

# 测试代码
if __name__ == "__main__":
    solution = Solution()
    
    # 测试用例1
    s1 = "aab"
    print(f"输入: s = {s1}")
    print(f"输出: {solution.partition(s1)}")
    
    # 测试用例2
    s2 = "a"
    print(f"\n输入: s = {s2}")
    print(f"输出: {solution.partition(s2)}") 